{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Odd Even Jump"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #dynamic-programming #ordered-set #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #动态规划 #有序集合 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: oddEvenJumps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #奇偶跳"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>A</code>，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。</p>\n",
    "\n",
    "<p>你可以按以下方式从索引 <code>i</code>&nbsp;向后跳转到索引 <code>j</code>（其中 <code>i &lt; j</code>）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在进行奇数跳跃时（如，第&nbsp;1，3，5... 次跳跃），你将会跳到索引 <code>j</code>，使得 <code>A[i] &lt;=&nbsp;A[j]</code>，<code>A[j]</code> 是可能的最小值。如果存在多个这样的索引 <code>j</code>，你只能跳到满足要求的<strong>最小</strong>索引 <code>j</code> 上。</li>\n",
    "\t<li>在进行偶数跳跃时（如，第&nbsp;2，4，6... 次跳跃），你将会跳到索引&nbsp;<code>j</code>，使得 <code>A[i] &gt;= A[j]</code>，<code>A[j]</code> 是可能的最大值。如果存在多个这样的索引 <code>j</code>，你只能跳到满足要求的<strong>最小</strong>索引 <code>j</code>&nbsp;上。</li>\n",
    "\t<li>（对于某些索引 <code>i</code>，可能无法进行合乎要求的跳跃。）</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 <code>A.length - 1</code>），那么该索引就会被认为是好的起始索引。</p>\n",
    "\n",
    "<p>返回好的起始索引的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[10,13,12,14,15]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释： </strong>\n",
    "从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 A[2] 是 A[1]，A[2]，A[3]，A[4] 中大于或等于 A[0] 的最小值），然后我们就无法继续跳下去了。\n",
    "从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。\n",
    "从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。\n",
    "从起始索引 i = 4 出发，我们已经到达数组末尾。\n",
    "总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[2,3,1,1,4]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：\n",
    "\n",
    "在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大于或等于 A[0] 的最小值。\n",
    "\n",
    "在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 A[2] 是（A[2]，A[3]，A[4]）中小于或等于 A[1] 的最大值。A[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。\n",
    "\n",
    "在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值。\n",
    "\n",
    "我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。\n",
    "\n",
    "类似地，我们可以推断：\n",
    "从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。\n",
    "从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。\n",
    "从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。\n",
    "从起始索引 i = 4 出发，我们已经到达数组末尾。\n",
    "总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[5,1,3,4,2]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释： </strong>\n",
    "我们可以从起始索引 1，2，4 出发到达数组末尾。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= A.length &lt;= 20000</code></li>\n",
    "\t<li><code>0 &lt;= A[i] &lt; 100000</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [odd-even-jump](https://leetcode.cn/problems/odd-even-jump/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [odd-even-jump](https://leetcode.cn/problems/odd-even-jump/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,13,12,14,15]', '[2,3,1,1,4]', '[5,1,3,4,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        low, high = [0] * n, [0] * n\n",
    "        \n",
    "        stack = []\n",
    "        for i, x in sorted(enumerate(arr), key=lambda x: (x[1], x[0])):\n",
    "            while stack and stack[-1] < i:\n",
    "                high[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i, x in sorted(enumerate(arr), key=lambda x: (-x[1], x[0])):\n",
    "            while stack and stack[-1] < i:\n",
    "                low[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        \n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        dp[-1] = [1] * 2\n",
    "        ans = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            dp[i][0] = dp[high[i]][1]\n",
    "            dp[i][1] = dp[low[i]][0]\n",
    "            ans += dp[i][0]\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ji = [False]*(n-1) + [True]\n",
    "        ou = [False]*(n-1) + [True]\n",
    "        stack = []\n",
    "        idx = []\n",
    "        idx2 = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            where1 = bisect_left(stack, arr[i])\n",
    "            if where1 != len(stack):\n",
    "                ji[i] = max(ji[i], ou[idx[where1]])\n",
    "            where2 = bisect_right(stack, arr[i])\n",
    "            if where2 != 0:\n",
    "                ou[i] = max(ou[i], ji[idx2[where2-1]])\n",
    "            stack.insert(where1, arr[i])\n",
    "            idx.insert(where1, i)\n",
    "            idx2.insert(where2, i)\n",
    "        return sum(ji)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        def getNext(nums: list) -> list:\n",
    "            res = [-1] * n\n",
    "            stk = []\n",
    "            for i in nums:\n",
    "                while stk and stk[-1] < i:\n",
    "                    res[stk.pop()] = i\n",
    "                stk.append(i)\n",
    "            return res\n",
    "        \n",
    "        idx = sorted(range(n), key = lambda x: arr[x])\n",
    "        oddnext = getNext(idx)\n",
    "        idx.sort(key = lambda x: -arr[x])\n",
    "        evennext = getNext(idx)\n",
    "\n",
    "        odd = [False] * n\n",
    "        even = [False] * n\n",
    "        odd[n - 1] = even[n - 1] = True\n",
    "        ans = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if oddnext[i] != -1:\n",
    "                odd[i] = even[oddnext[i]]\n",
    "            if evennext[i] != -1:\n",
    "                even[i] = odd[evennext[i]]\n",
    "            if odd[i]: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 单调栈\n",
    "    def oddEvenJumps(self, A: List[int]) -> int:\n",
    "        N = len(A)\n",
    "\n",
    "        def make(B: List[int]) -> int:\n",
    "            ans = [None] * N\n",
    "            stack = []  # invariant: stack is decreasing\n",
    "            for i in B:\n",
    "                while stack and i > stack[-1]:\n",
    "                    ans[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "            return ans\n",
    "\n",
    "        B = sorted(range(N), key = lambda i: A[i])\n",
    "        oddnext = make(B)\n",
    "        B.sort(key = lambda i: -A[i])\n",
    "        evennext = make(B)\n",
    "\n",
    "        odd = [False] * N\n",
    "        even = [False] * N\n",
    "        odd[N-1] = even[N-1] = True\n",
    "\n",
    "        for i in range(N-2, -1, -1):\n",
    "            if oddnext[i] is not None:\n",
    "                odd[i] = even[oddnext[i]]\n",
    "            if evennext[i] is not None:\n",
    "                even[i] = odd[evennext[i]]\n",
    "\n",
    "        return sum(odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # 从右向左\n",
    "        n = len(arr)\n",
    "        # dpOdd[i]表示从位置i,进行奇数跳跃,是否能到达末尾\n",
    "        # dpEven[i]表示偶数跳跃\n",
    "        dpOdd =[False] * n\n",
    "        dpEven = [False] * n\n",
    "        # 从末尾跳跃总是可以的\n",
    "        dpOdd[-1] = True\n",
    "        dpEven[-1] = True\n",
    "        stack = [(arr[n - 1],n - 1)]\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            p = bisect.bisect_left(stack,(arr[i],i))\n",
    "            if p < len(stack):\n",
    "                val,idx = stack[p]\n",
    "                if val == arr[i]:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    dpEven[i] = dpOdd[idx]\n",
    "                    stack[p] = (arr[i],i)\n",
    "                else:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    stack.insert(p,(arr[i],i))\n",
    "                    if p > 0:\n",
    "                        dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "            else:   # p == len(stack)\n",
    "                dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "                stack.insert(p,(arr[i],i))\n",
    "        #print(dpOdd)\n",
    "        #print(dpEven)\n",
    "        return sum(dpOdd)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # 从右向左\n",
    "        n = len(arr)\n",
    "        # dpOdd[i]表示从位置i,进行奇数跳跃,是否能到达末尾\n",
    "        # dpEven[i]表示偶数跳跃\n",
    "        dpOdd =[False] * n\n",
    "        dpEven = [False] * n\n",
    "        # 从末尾跳跃总是可以的\n",
    "        dpOdd[-1] = True\n",
    "        dpEven[-1] = True\n",
    "        stack = [(arr[n - 1],n - 1)]\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            p = bisect.bisect_left(stack,(arr[i],i))\n",
    "            if p < len(stack):\n",
    "                val,idx = stack[p]\n",
    "                if val == arr[i]:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    dpEven[i] = dpOdd[idx]\n",
    "                    stack[p] = (arr[i],i)\n",
    "                else:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    stack.insert(p,(arr[i],i))\n",
    "                    if p > 0:\n",
    "                        dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "            else:   # p == len(stack)\n",
    "                dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "                stack.insert(p,(arr[i],i))\n",
    "        #print(dpOdd)\n",
    "        #print(dpEven)\n",
    "        return sum(dpOdd)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # 用2个单调栈会比二分查找更快\n",
    "        # 单调栈...待实现\n",
    "\n",
    "        # 二分查找\n",
    "        # 从右向左\n",
    "        n = len(arr)\n",
    "        # dpOdd[i]表示从位置i,进行奇数跳跃,是否能到达末尾\n",
    "        # dpEven[i]表示偶数跳跃\n",
    "        dpOdd =[False] * n\n",
    "        dpEven = [False] * n\n",
    "        # 从末尾跳跃总是可以的\n",
    "        dpOdd[-1] = True\n",
    "        dpEven[-1] = True\n",
    "        stack = [(arr[n - 1],n - 1)]\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            p = bisect.bisect_left(stack,(arr[i],i))\n",
    "            if p < len(stack):\n",
    "                val,idx = stack[p]\n",
    "                if val == arr[i]:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    dpEven[i] = dpOdd[idx]\n",
    "                    stack[p] = (arr[i],i)\n",
    "                else:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    stack.insert(p,(arr[i],i))\n",
    "                    if p > 0:\n",
    "                        dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "            else:   # p == len(stack)\n",
    "                dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "                stack.insert(p,(arr[i],i))\n",
    "        #print(dpOdd)\n",
    "        #print(dpEven)\n",
    "        return sum(dpOdd)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def oddEvenJumps(self, A):\n",
    "        N = len(A)\n",
    "\n",
    "        def make(B):\n",
    "            ans = [None] * N\n",
    "            stack = []  # invariant: stack is decreasing\n",
    "            for i in B:\n",
    "                while stack and i > stack[-1]:\n",
    "                    ans[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "            return ans\n",
    "\n",
    "        B = sorted(range(N), key = lambda i: A[i])\n",
    "        oddnext = make(B)\n",
    "        B.sort(key = lambda i: -A[i])\n",
    "        evennext = make(B)\n",
    "\n",
    "        odd = [False] * N\n",
    "        even = [False] * N\n",
    "        odd[N-1] = even[N-1] = True\n",
    "\n",
    "        for i in range(N-2, -1, -1):\n",
    "            if oddnext[i] is not None:\n",
    "                odd[i] = even[oddnext[i]]\n",
    "            if evennext[i] is not None:\n",
    "                even[i] = odd[evennext[i]]\n",
    "\n",
    "        return sum(odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        n = len(arr)\n",
    "        \n",
    "        def jump_path(sorted_index):\n",
    "            jump_next = [None] * n\n",
    "            stack = []\n",
    "            for i in sorted_index:\n",
    "                while stack and i > stack[-1]:\n",
    "                    jump_next[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "            return jump_next\n",
    "        \n",
    "        index_sort = sorted(range(n), key=lambda i: arr[i])\n",
    "        odd_jump = jump_path(index_sort)\n",
    "        index_sort.sort(key=lambda i: -arr[i])\n",
    "        even_jump = jump_path(index_sort)\n",
    "        \n",
    "        odd = [False] * n\n",
    "        even = [False] * n\n",
    "\n",
    "        odd[n-1], even[n-1] = True, True\n",
    "        \n",
    "        for i in range(n-2, -1, -1):\n",
    "            if odd_jump[i]:\n",
    "                odd[i] = even[odd_jump[i]]\n",
    "            if even_jump[i]:\n",
    "                even[i] = odd[even_jump[i]]\n",
    "\n",
    "        return sum(odd)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        def find_idx(nums):\n",
    "            ans = [None] * n\n",
    "            stack = []\n",
    "            for x in nums:\n",
    "                while stack and x > stack[-1]:\n",
    "                    ans[stack.pop()] = x\n",
    "                stack.append(x)\n",
    "            return ans\n",
    "        \n",
    "        nums = sorted(range(n), key = lambda x: arr[x])\n",
    "        odd_idx = find_idx(nums)\n",
    "        nums.sort(key = lambda x: -arr[x])\n",
    "        even_idx = find_idx(nums)\n",
    "\n",
    "        odd = [False] * n\n",
    "        even = [False] * n\n",
    "        odd[-1] = even[-1] = True\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if odd_idx[i]:\n",
    "                odd[i] = even[odd_idx[i]]\n",
    "            if even_idx[i]:\n",
    "                even[i] = odd[even_idx[i]]\n",
    "        return sum(odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # sort indexes based on arr value\n",
    "        l = len(arr)\n",
    "\n",
    "        def transitions(indexes: List[int]) -> List[int]:\n",
    "            queue = deque([])\n",
    "            jumps = [None] * l\n",
    "            for j in indexes:\n",
    "                while queue and queue[-1] < j:\n",
    "                    jumps[queue.pop()] = j # odd jump index transition from i to j\n",
    "                \n",
    "                queue.append(j)\n",
    "            return jumps\n",
    "\n",
    "        indexes = [i for i in range(l)]\n",
    "        indexes.sort(key = lambda i: arr[i])    # sort asc based on arr val\n",
    "        odd_jumps = transitions(indexes)\n",
    "        indexes.sort(key = lambda i: -arr[i])    # sort asc based on arr val\n",
    "        even_jumps = transitions(indexes) # reverse sorting to get even jumps\n",
    "\n",
    "        odd_steps, even_steps = [False] * l, [False] * l\n",
    "        odd_steps[-1], even_steps[-1] = True, True\n",
    "\n",
    "        for i in range(l - 2, -1, -1):\n",
    "            if odd_jumps[i] is not None:    # propagate backwards if possible\n",
    "                j = odd_jumps[i]\n",
    "                odd_steps[i] = even_steps[j]\n",
    "            if even_jumps[i] is not None:\n",
    "                j = even_jumps[i]\n",
    "                even_steps[i] = odd_steps[j]\n",
    "        \n",
    "        return sum(odd_steps)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # 用2个单调栈会比二分查找更快\n",
    "        # 单调栈\n",
    "        # 从右到左\n",
    "        n = len(arr)\n",
    "        # dpOdd[i]表示从位置i,进行奇数跳跃,是否能到达末尾\n",
    "        # dpEven[i]表示偶数跳跃\n",
    "        dpOdd =[False] * n\n",
    "        dpEven = [False] * n\n",
    "        # 从末尾跳跃总是可以的\n",
    "        dpOdd[-1] = True\n",
    "        dpEven[-1] = True\n",
    "        \n",
    "        def helper(nxt):\n",
    "            res = [None] * n\n",
    "            stack = list()  # 降序\n",
    "            for i in nxt:\n",
    "                while stack and i > stack[-1]:\n",
    "                    res[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "            return res\n",
    "\n",
    "        nxt = sorted(range(n),key = lambda i:arr[i])\n",
    "        oddNext = helper(nxt)\n",
    "        nxt.sort(key = lambda i: -arr[i])\n",
    "        evenNext = helper(nxt)\n",
    "\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            if oddNext[i] is not None:\n",
    "                dpOdd[i] = dpEven[oddNext[i]]\n",
    "            if evenNext[i] is not None:\n",
    "                dpEven[i] = dpOdd[evenNext[i]]\n",
    "            #print(i)\n",
    "            #print(dpOdd)\n",
    "            #print(dpEven)\n",
    "        return sum(dpOdd)\n",
    "\n",
    "        # 二分查找\n",
    "        # 从右向左\n",
    "        n = len(arr)\n",
    "        # dpOdd[i]表示从位置i,进行奇数跳跃,是否能到达末尾\n",
    "        # dpEven[i]表示偶数跳跃\n",
    "        dpOdd =[False] * n\n",
    "        dpEven = [False] * n\n",
    "        # 从末尾跳跃总是可以的\n",
    "        dpOdd[-1] = True\n",
    "        dpEven[-1] = True\n",
    "        stack = [(arr[n - 1],n - 1)]\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            p = bisect.bisect_left(stack,(arr[i],i))\n",
    "            if p < len(stack):\n",
    "                val,idx = stack[p]\n",
    "                if val == arr[i]:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    dpEven[i] = dpOdd[idx]\n",
    "                    stack[p] = (arr[i],i)\n",
    "                else:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    stack.insert(p,(arr[i],i))\n",
    "                    if p > 0:\n",
    "                        dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "            else:   # p == len(stack)\n",
    "                dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "                stack.insert(p,(arr[i],i))\n",
    "        #print(dpOdd)\n",
    "        #print(dpEven)\n",
    "        return sum(dpOdd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # 用2个单调栈会比二分查找更快\n",
    "        # 单调栈\n",
    "        # 从右到左\n",
    "        n = len(arr)\n",
    "        # dpOdd[i]表示从位置i,进行奇数跳跃,是否能到达末尾\n",
    "        # dpEven[i]表示偶数跳跃\n",
    "        dpOdd =[False] * n\n",
    "        dpEven = [False] * n\n",
    "        # 从末尾跳跃总是可以的\n",
    "        dpOdd[-1] = True\n",
    "        dpEven[-1] = True\n",
    "        \n",
    "        def helper(nxt):\n",
    "            res = [None] * n\n",
    "            stack = list()  # 降序\n",
    "            for i in nxt:\n",
    "                while stack and i > stack[-1]:\n",
    "                    res[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "            return res\n",
    "\n",
    "        nxt = sorted(range(n),key = lambda i:arr[i])\n",
    "        oddNext = helper(nxt)\n",
    "        nxt.sort(key = lambda i: -arr[i])\n",
    "        evenNext = helper(nxt)\n",
    "\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            if oddNext[i] is not None:\n",
    "                dpOdd[i] = dpEven[oddNext[i]]\n",
    "            if evenNext[i] is not None:\n",
    "                dpEven[i] = dpOdd[evenNext[i]]\n",
    "            #print(i)\n",
    "            #print(dpOdd)\n",
    "            #print(dpEven)\n",
    "        return sum(dpOdd)\n",
    "\n",
    "        # 二分查找\n",
    "        # 从右向左\n",
    "        n = len(arr)\n",
    "        # dpOdd[i]表示从位置i,进行奇数跳跃,是否能到达末尾\n",
    "        # dpEven[i]表示偶数跳跃\n",
    "        dpOdd =[False] * n\n",
    "        dpEven = [False] * n\n",
    "        # 从末尾跳跃总是可以的\n",
    "        dpOdd[-1] = True\n",
    "        dpEven[-1] = True\n",
    "        stack = [(arr[n - 1],n - 1)]\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            p = bisect.bisect_left(stack,(arr[i],i))\n",
    "            if p < len(stack):\n",
    "                val,idx = stack[p]\n",
    "                if val == arr[i]:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    dpEven[i] = dpOdd[idx]\n",
    "                    stack[p] = (arr[i],i)\n",
    "                else:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    stack.insert(p,(arr[i],i))\n",
    "                    if p > 0:\n",
    "                        dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "            else:   # p == len(stack)\n",
    "                dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "                stack.insert(p,(arr[i],i))\n",
    "        #print(dpOdd)\n",
    "        #print(dpEven)\n",
    "        return sum(dpOdd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # 用2个单调栈会比二分查找更快\n",
    "        # 单调栈\n",
    "        # 从右到左\n",
    "        n = len(arr)\n",
    "        # dpOdd[i]表示从位置i,进行奇数跳跃,是否能到达末尾\n",
    "        # dpEven[i]表示偶数跳跃\n",
    "        dpOdd =[False] * n\n",
    "        dpEven = [False] * n\n",
    "        # 从末尾跳跃总是可以的\n",
    "        dpOdd[-1] = True\n",
    "        dpEven[-1] = True\n",
    "        \n",
    "        def helper(nxt):\n",
    "            res = [None] * n\n",
    "            stack = list()\n",
    "            for i in nxt:\n",
    "                while stack and i > stack[-1]:\n",
    "                    res[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "            return res\n",
    "\n",
    "        nxt = sorted(range(n),key = lambda i:arr[i])\n",
    "        oddNext = helper(nxt)\n",
    "        nxt.sort(key = lambda i: -arr[i])\n",
    "        evenNext = helper(nxt)\n",
    "\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            if oddNext[i] is not None:\n",
    "                dpOdd[i] = dpEven[oddNext[i]]\n",
    "            if evenNext[i] is not None:\n",
    "                dpEven[i] = dpOdd[evenNext[i]]\n",
    "            #print(i)\n",
    "            #print(dpOdd)\n",
    "            #print(dpEven)\n",
    "        return sum(dpOdd)\n",
    "\n",
    "        # 二分查找\n",
    "        # 从右向左\n",
    "        n = len(arr)\n",
    "        # dpOdd[i]表示从位置i,进行奇数跳跃,是否能到达末尾\n",
    "        # dpEven[i]表示偶数跳跃\n",
    "        dpOdd =[False] * n\n",
    "        dpEven = [False] * n\n",
    "        # 从末尾跳跃总是可以的\n",
    "        dpOdd[-1] = True\n",
    "        dpEven[-1] = True\n",
    "        stack = [(arr[n - 1],n - 1)]\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            p = bisect.bisect_left(stack,(arr[i],i))\n",
    "            if p < len(stack):\n",
    "                val,idx = stack[p]\n",
    "                if val == arr[i]:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    dpEven[i] = dpOdd[idx]\n",
    "                    stack[p] = (arr[i],i)\n",
    "                else:\n",
    "                    dpOdd[i] = dpEven[idx]\n",
    "                    stack.insert(p,(arr[i],i))\n",
    "                    if p > 0:\n",
    "                        dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "            else:   # p == len(stack)\n",
    "                dpEven[i] = dpOdd[stack[p - 1][1]]\n",
    "                stack.insert(p,(arr[i],i))\n",
    "        #print(dpOdd)\n",
    "        #print(dpEven)\n",
    "        return sum(dpOdd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        def auxFun(lst):\n",
    "            stack = []\n",
    "            indexs = [None] * N\n",
    "            for i in lst:\n",
    "                while stack and i > stack[-1]:\n",
    "                    indexs[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "            \n",
    "            return indexs\n",
    "            \n",
    "\n",
    "        N = len(arr)\n",
    "        lst = sorted(range(N), key=lambda i: arr[i])\n",
    "        oddIndexs = auxFun(lst)\n",
    "        lst = sorted(range(N), key=lambda i: -arr[i])\n",
    "        evenIndexs = auxFun(lst)\n",
    "        \n",
    "        odd = [False] * N\n",
    "        even = [False] * N\n",
    "        odd[N-1] = even[N-1] = True\n",
    "        for idx in range(N-2, -1, -1):\n",
    "            if oddIndexs[idx] is not None:\n",
    "                odd[idx] = even[oddIndexs[idx]]\n",
    "            if evenIndexs[idx] is not None:\n",
    "                even[idx] = odd[evenIndexs[idx]]\n",
    "        \n",
    "        return sum(odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # 把问题拆为两个部分： （1）每个元素之后第一个大于等于（小于等于）它的值。这是一个用单调栈解决的经典问题。 （2）每个元素作为第奇数步/偶数步之后能不能到达目标点。这完全由它后面一个偶数步/奇数步点决定。倒序DP\n",
    "\n",
    "        n = len(arr)\n",
    "        indexSortedByValAsc = sorted(range(n), key = lambda i : arr[i])\n",
    "        indexSortedByValDesc = sorted(range(n), key = lambda i : -arr[i])\n",
    "        oddNextJump = self.getNextJump(indexSortedByValAsc)\n",
    "        evenNextJump = self.getNextJump(indexSortedByValDesc)\n",
    "\n",
    "        odd = [False] * n \n",
    "        even = [False] * n\n",
    "        odd[-1] = True\n",
    "        even[-1] = True\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if oddNextJump[i]:\n",
    "                odd[i] = even[oddNextJump[i]]\n",
    "            if evenNextJump[i]:\n",
    "                even[i] = odd[evenNextJump[i]]\n",
    "\n",
    "        return sum(odd)\n",
    "\n",
    "\n",
    "    def getNextJump(self, indexSortedByVal):\n",
    "        ans = [None] * len(indexSortedByVal)\n",
    "        stack = []\n",
    "        #单调递减站\n",
    "        for i in indexSortedByVal:\n",
    "            while stack and stack[-1] < i:\n",
    "                ans[stack.pop()] = i\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "\n",
    "        def make(B):\n",
    "            res = [0] * l\n",
    "            stack = []  # decreasing\n",
    "            for j in B: # jump from prev i to curr j\n",
    "                while stack and j > stack[-1]:\n",
    "                    i = stack.pop()\n",
    "                    res[i] = j\n",
    "                stack.append(j)\n",
    "            return res\n",
    "\n",
    "        odd_order = sorted(range(l), key = lambda i: arr[i])    # sort index based on value in arr, increasing index\n",
    "        even_order = sorted(range(l), key = lambda i: -arr[i])\n",
    "        # each shows next jump index\n",
    "        oddnext = make(odd_order)   # from current index to next index with increasing value\n",
    "        evennext = make(even_order) # from current index to next index with decreasing value\n",
    "\n",
    "        odd = [False] * l\n",
    "        even = [False] * l\n",
    "        odd[l - 1] = even[l - 1] = True\n",
    "        for i in range(l - 2, -1, -1):\n",
    "            if oddnext[i] is not None:  # odd jump case\n",
    "                j = oddnext[i]\n",
    "                odd[i] = even[j]\n",
    "            if evennext[i] is not None: # even jump case\n",
    "                j = evennext[i]\n",
    "                even[i] = odd[j]\n",
    "\n",
    "        return sum(odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "\n",
    "        def make(B):\n",
    "            res = [0] * l\n",
    "            stack = []  # decreasing\n",
    "            for j in B: # jump from prev i to curr j\n",
    "                while stack and j > stack[-1]:\n",
    "                    i = stack.pop()\n",
    "                    res[i] = j\n",
    "                stack.append(j)\n",
    "            return res\n",
    "\n",
    "        odd_order = sorted(range(l), key = lambda i: arr[i])    # sort index based on value in arr, increasing index\n",
    "        even_order = sorted(range(l), key = lambda i: -arr[i])\n",
    "        # each shows next jump index\n",
    "        oddnext = make(odd_order)   # from current index to next index with increasing value\n",
    "        evennext = make(even_order) # from current index to next index with decreasing value\n",
    "\n",
    "        odd = [False] * l\n",
    "        even = [False] * l\n",
    "        odd[l - 1] = even[l - 1] = True \n",
    "        # represent starting each idx, with current step odd or even jump, wether it's possible to arrive at dest\n",
    "        # state iterated backwards\n",
    "        for i in range(l - 2, -1, -1):\n",
    "            if oddnext[i] is not None:  # case: odd jump to even step\n",
    "                j = oddnext[i]\n",
    "                odd[i] = even[j]\n",
    "            if evennext[i] is not None: # case: even jump to odd step\n",
    "                j = evennext[i]\n",
    "                even[i] = odd[j]\n",
    "\n",
    "        return sum(odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "\n",
    "        def make(B):\n",
    "            res = [0] * l\n",
    "            stack = []  # decreasing\n",
    "            for j in B: # jump from prev i to curr j\n",
    "                while stack and j > stack[-1]:\n",
    "                    i = stack.pop()\n",
    "                    res[i] = j\n",
    "                stack.append(j)\n",
    "            return res\n",
    "\n",
    "        odd_order = sorted(range(l), key = lambda i: arr[i])    # sort index based on value in arr, increasing index\n",
    "        even_order = sorted(range(l), key = lambda i: -arr[i])\n",
    "        # each shows next jump index\n",
    "        oddnext = make(odd_order)   # from current index to next index with increasing value\n",
    "        evennext = make(even_order) # from current index to next index with decreasing value\n",
    "\n",
    "        odd = [False] * l\n",
    "        even = [False] * l\n",
    "        odd[l - 1] = even[l - 1] = True \n",
    "        # represent starting each idx, with current step odd or even jump, wether it's possible to arrive at dest\n",
    "        for i in range(l - 2, -1, -1):\n",
    "            if oddnext[i] is not None:  # odd jump case\n",
    "                j = oddnext[i]\n",
    "                odd[i] = even[j]\n",
    "            if evennext[i] is not None: # even jump case\n",
    "                j = evennext[i]\n",
    "                even[i] = odd[j]\n",
    "\n",
    "        return sum(odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        def next(s):\n",
    "            ans = [None] * n\n",
    "            stack = []\n",
    "            for i in s:\n",
    "                while stack and stack[-1] < i:\n",
    "                    ans[stack[-1]] = i\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "            return ans\n",
    "        \n",
    "        s = sorted(range(n), key = lambda x: arr[x])\n",
    "        oddnext = next(s)\n",
    "        s = sorted(range(n), key=lambda x: -arr[x])\n",
    "        evennext = next(s)\n",
    "\n",
    "        odd = [False] * n\n",
    "        even = [False] * n\n",
    "        odd[n - 1] = even[n - 1] = True\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if oddnext[i]:\n",
    "                odd[i] = even[oddnext[i]]\n",
    "            if evennext[i]:\n",
    "                even[i] = odd[evennext[i]]\n",
    "            \n",
    "        return sum(odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        p = sorted(range(n),key=lambda i:arr[i])\n",
    "        oddn = [None]*n\n",
    "        stack = []\n",
    "        for i in p:\n",
    "            while stack and stack[-1]<i:\n",
    "                oddn[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        evenn = [None]*n\n",
    "        p = sorted(range(n),key=lambda i:-arr[i])\n",
    "        stack = []\n",
    "        for i in p:\n",
    "            while stack and stack[-1]<i:\n",
    "                evenn[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        odd = [False]*n\n",
    "        even = [False]*n\n",
    "        odd[n-1] = even[n-1] = True\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if oddn[i]!=None:\n",
    "                odd[i] = even[oddn[i]]\n",
    "            if evenn[i] != None:\n",
    "                even[i] = odd[evenn[i]]\n",
    "        return sum(odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        valIncreIndexes = sorted([i for i in range(n)], key=lambda x: arr[x])\n",
    "        valDecreIndexes = sorted([i for i in range(n)], key=lambda x: -arr[x])\n",
    "        # print(valDecreIndexes, valIncreIndexes[::-1])\n",
    "        # 注意sorted([i for i in range(n)], key=lambda x: -arr[x])和sorted([i for i in range(n)], key=lambda x: arr[x])[::-1]的区别是，前者在arr[x]是相等的情况下，会按照x的顺序来排序，但是后者则是按照x的逆序来排序\n",
    "\n",
    "        def generateNextJump(indexes):\n",
    "            res = [-1] * n \n",
    "            stack = []\n",
    "            for index in indexes:\n",
    "                while stack and index > stack[-1]:\n",
    "                    res[stack.pop()] = index \n",
    "                stack.append(index)\n",
    "            return res\n",
    "        \n",
    "        oddNext = generateNextJump(valIncreIndexes)\n",
    "        evenNext = generateNextJump(valDecreIndexes)\n",
    "        odd = [False] * n \n",
    "        even = [False] * n \n",
    "        odd[n-1] = even[n-1] = True\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if oddNext[i] != -1:\n",
    "                odd[i] = even[oddNext[i]]\n",
    "            if evenNext[i] != -1:\n",
    "                even[i] = odd[evenNext[i]]\n",
    "        \n",
    "        return sum(odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# in the case of an odd jump\r\n",
    "# arr[j] can be arrived from arr[i], where arr[i] <= arr[j] and\r\n",
    "# arr[j] is minimum value in arr[j:], and\r\n",
    "# in the case of an even jump\r\n",
    "# arr[j] can be arrived from arr[i], where arr[i] >= arr[j] and\r\n",
    "# arr[j] is maximum value in arr[j:], and\r\n",
    "# with reversed traversal for sorted list, valid i->j pairs can be found\r\n",
    "# finally find all valid starting index as a path of odd - even - ...\r\n",
    "from sortedcontainers import SortedDict\r\n",
    "class Solution:\r\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\r\n",
    "        res = 1\r\n",
    "        n = len(arr)\r\n",
    "        sd: dict[int, list[bool]] = SortedDict({arr[-1]: [True, True]})\r\n",
    "\r\n",
    "        for i in range(n - 2, -1, -1):\r\n",
    "            if arr[i] in sd:\r\n",
    "                sd[arr[i]] = sd[arr[i]][::-1]\r\n",
    "            else:\r\n",
    "                x = sd.bisect_left(arr[i])\r\n",
    "                sd.setdefault(arr[i], [x > 0 and sd.values()[x - 1][1], x < len(sd) and sd.values()[x][0]])\r\n",
    "            if sd[arr[i]][1]:\r\n",
    "                res += 1\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, A: List[int]) -> int:\n",
    "        def make_jump_indices(order):\n",
    "            result = [0] * len(A)\n",
    "            stack = []\n",
    "            for i in order:\n",
    "                while stack and stack[-1] < i:\n",
    "                    result[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "            return result\n",
    "\n",
    "        n = len(A)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        odd_next = make_jump_indices(sorted(range(n), key=lambda i: (A[i], i)))\n",
    "        even_next = make_jump_indices(sorted(range(n), key=lambda i: (-A[i], i)))\n",
    "\n",
    "        odd_reachable = [False] * n\n",
    "        even_reachable = [False] * n\n",
    "        odd_reachable[-1] = even_reachable[-1] = True\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            odd_reachable[i] = even_reachable[odd_next[i]]\n",
    "            even_reachable[i] = odd_reachable[even_next[i]]\n",
    "\n",
    "        return sum(odd_reachable)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "        dp = [[False, False] for i in range(l)]#记录每个点奇数次和偶数次跳跃是否能到达终点\n",
    "        dp[-1] = [True, True]#终点一定是可以到达的,无论奇数还是偶数\n",
    "        res = 1#终点一定可以到达,所以初始化为1\n",
    "        s = [arr[-1]]#排序数组\n",
    "        d = {arr[-1]:l - 1}#哈希表\n",
    "        for i in range(l - 2, -1, -1):#跳过终点倒序遍历\n",
    "            idx = bisect.bisect_left(s, arr[i])#二分查找奇数次跳跃要到达的值\n",
    "            if idx < len(s):#如果有比当前值大的值\n",
    "                dp[i][0] = dp[d[s[idx]]][1]#通过哈希表映射 该点的偶数次跳跃是否能够到达终点\n",
    "            if idx < len(s) and s[idx] == arr[i]:#如果值相等,那么偶数次跳跃所到达的值相同\n",
    "                dp[i][1] = dp[d[s[idx]]][0]\n",
    "            else:#否则值不同\n",
    "                if idx != 0:#如果存在更小值\n",
    "                    dp[i][1] = dp[d[s[idx - 1]]][0]#通过哈希表映射该点的奇数次跳跃是否能够到达终点\n",
    "                s.insert(idx, arr[i])#由于值不同,插入当前值\n",
    "            d[s[idx]] = i#更新哈希表\n",
    "            if dp[i][0]:#如果该点奇数次跳跃能到达终点,结果+1\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "\n",
    "        ids=[i for i in range(n)]\n",
    "        ids.sort(key=lambda i: (arr[i], i))\n",
    "        odd_nxt=[-1 for _ in range(n)]\n",
    "        decstk=[]\n",
    "        for i in ids:\n",
    "            while decstk and decstk[-1]<i:\n",
    "                odd_nxt[decstk.pop(-1)]=i\n",
    "            decstk.append(i)\n",
    "        \n",
    "        ids.sort(key=lambda i: (-arr[i],i))\n",
    "        even_nxt=[-1 for _ in range(n)]\n",
    "        incstk=[]\n",
    "        for i in ids:\n",
    "            while incstk and incstk[-1]<i:\n",
    "                even_nxt[incstk.pop(-1)]=i\n",
    "            incstk.append(i)\n",
    "        \n",
    "        odd=[False for _ in range(n)]\n",
    "        even=[False for _ in range(n)]\n",
    "        odd[n-1]=True\n",
    "        even[n-1]=True\n",
    "\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if odd_nxt[i]!=-1:\n",
    "                odd[i]=even[odd_nxt[i]]\n",
    "            if even_nxt[i]!=-1:\n",
    "                even[i]=odd[even_nxt[i]]\n",
    "\n",
    "        return sum(odd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "        dp = [[False, False] for i in range(l)]#记录每个点奇数次和偶数次跳跃是否能到达终点\n",
    "        dp[-1] = [True, True]#终点一定是可以到达的,无论奇数还是偶数\n",
    "        res = 1#终点一定可以到达,所以初始化为1\n",
    "        s = [arr[-1]]#排序数组\n",
    "        d = {arr[-1]:l - 1}#哈希表\n",
    "        for i in range(l - 2, -1, -1):#跳过终点倒序遍历\n",
    "            idx = bisect.bisect_left(s, arr[i])#二分查找奇数次跳跃要到达的值\n",
    "            if idx < len(s):#如果有比当前值大的值\n",
    "                dp[i][0] = dp[d[s[idx]]][1]#通过哈希表映射 该点的偶数次跳跃是否能够到达终点\n",
    "            if idx < len(s) and s[idx] == arr[i]:#如果值相等,那么偶数次跳跃所到达的值相同\n",
    "                dp[i][1] = dp[d[s[idx]]][0]\n",
    "            else:#否则值不同\n",
    "                if idx != 0:#如果存在更小值\n",
    "                    dp[i][1] = dp[d[s[idx - 1]]][0]#通过哈希表映射该点的奇数次跳跃是否能够到达终点\n",
    "                s.insert(idx, arr[i])#由于值不同,插入当前值\n",
    "            d[s[idx]] = i#更新哈希表\n",
    "            if dp[i][0]:#如果该点奇数次跳跃能到达终点,结果+1\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "        dp = [[False, False] for i in range(l)]#记录每个点奇数次和偶数次跳跃是否能到达终点\n",
    "        dp[-1] = [True, True]#终点一定是可以到达的,无论奇数还是偶数\n",
    "        res = 1#终点一定可以到达,所以初始化为1\n",
    "        s = [arr[-1]]#排序数组\n",
    "        d = {arr[-1]:l - 1}#哈希表\n",
    "        for i in range(l - 2, -1, -1):#跳过终点倒序遍历\n",
    "            idx = bisect.bisect_left(s, arr[i])#二分查找奇数次跳跃要到达的值\n",
    "            if idx < len(s):#如果有比当前值大的值\n",
    "                dp[i][0] = dp[d[s[idx]]][1]#通过哈希表映射 该点的偶数次跳跃是否能够到达终点\n",
    "            if idx < len(s) and s[idx] == arr[i]:#如果值相等,那么偶数次跳跃所到达的值相同\n",
    "                dp[i][1] = dp[d[s[idx]]][0]\n",
    "            else:#否则值不同\n",
    "                if idx != 0:#如果存在更小值\n",
    "                    dp[i][1] = dp[d[s[idx - 1]]][0]#通过哈希表映射该点的奇数次跳跃是否能够到达终点\n",
    "                s.insert(idx, arr[i])#由于值不同,插入当前值\n",
    "            d[s[idx]] = i#更新哈希表\n",
    "            if dp[i][0]:#如果该点奇数次跳跃能到达终点,结果+1\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# in the case of an odd jump\r\n",
    "# arr[j] can be arrived from arr[i], where arr[i] <= arr[j] and\r\n",
    "# arr[j] is minimum value in arr[j:], and\r\n",
    "# in the case of an even jump\r\n",
    "# arr[j] can be arrived from arr[i], where arr[i] >= arr[j] and\r\n",
    "# arr[j] is maximum value in arr[j:], and\r\n",
    "# with reversed traversal for sorted list, valid i->j pairs can be found\r\n",
    "# finally find all valid starting index as a path of odd - even - ...\r\n",
    "from sortedcontainers import SortedDict\r\n",
    "class Solution:\r\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        n = len(arr)\r\n",
    "        sd: dict[int, int] = SortedDict()\r\n",
    "        reachable = [[False] * 2 for _ in range(n)]\r\n",
    "        reachable[n - 1][0] = reachable[n - 1][1] = True\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            x = sd.bisect_left(arr[i])\r\n",
    "            if x < len(sd) and sd.keys()[x] == arr[i]:\r\n",
    "                reachable[i][0] = reachable[sd.values()[x]][1]\r\n",
    "                reachable[i][1] = reachable[sd.values()[x]][0]\r\n",
    "                sd[sd.keys()[x]] = i\r\n",
    "            else:\r\n",
    "                if x > 0:\r\n",
    "                    reachable[i][0] = reachable[sd.values()[x - 1]][1]\r\n",
    "                if x < len(sd):\r\n",
    "                    reachable[i][1] = reachable[sd.values()[x]][0]\r\n",
    "                sd.setdefault(arr[i], i)\r\n",
    "            if reachable[i][1]:\r\n",
    "                res += 1\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "        dp = [[False, False] for i in range(l)]#记录每个点奇数次和偶数次跳跃是否能到达终点\n",
    "        dp[-1] = [True, True]#终点一定是可以到达的,无论奇数还是偶数\n",
    "        res = 1#终点一定可以到达,所以初始化为1\n",
    "        s = [arr[-1]]#排序数组\n",
    "        d = {arr[-1]:l - 1}#哈希表\n",
    "        for i in range(l - 2, -1, -1):#跳过终点倒序遍历\n",
    "            idx = bisect.bisect_left(s, arr[i])#二分查找奇数次跳跃要到达的值\n",
    "            if idx < len(s):#如果有比当前值大的值\n",
    "                dp[i][0] = dp[d[s[idx]]][1]#通过哈希表映射 该点的偶数次跳跃是否能够到达终点\n",
    "            if idx < len(s) and s[idx] == arr[i]:#如果值相等,那么偶数次跳跃所到达的值相同\n",
    "                dp[i][1] = dp[d[s[idx]]][0]\n",
    "            else:#否则值不同\n",
    "                if idx != 0:#如果存在更小值\n",
    "                    dp[i][1] = dp[d[s[idx - 1]]][0]#通过哈希表映射该点的奇数次跳跃是否能够到达终点\n",
    "                s.insert(idx, arr[i])#由于值不同,插入当前值\n",
    "            d[s[idx]] = i#更新哈希表\n",
    "            if dp[i][0]:#如果该点奇数次跳跃能到达终点,结果+1\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        reach = [[0, 0] for _ in range(n)] #reach[i][0] == 1 表示从i出发，奇数次跳跃后能到达最后一个，reach[i][1]表示偶数次。。。\n",
    "\n",
    "        reach[-1] = [1, 1]\n",
    "        had = dict()\n",
    "        q = SortedList()\n",
    "        had[arr[-1]] = n - 1\n",
    "        q.add(arr[-1])\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            x = arr[i]\n",
    "            #奇数跳\n",
    "            index = q.bisect_left(x)\n",
    "            if index < len(q): \n",
    "                j = had[q[index]]\n",
    "                reach[i][0] = reach[j][1]\n",
    "\n",
    "            #偶数跳\n",
    "            index = q.bisect_right(x)\n",
    "            if index > 0:\n",
    "                j = had[q[index-1]]\n",
    "                reach[i][1] = reach[j][0]\n",
    "\n",
    "            if reach[i][0]:\n",
    "                ans += 1 \n",
    "\n",
    "\n",
    "            if x in had:\n",
    "                had[x] = i\n",
    "                continue\n",
    "            else:\n",
    "                had[x] = i\n",
    "                q.add(x)\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        reach = [[0, 0] for _ in range(n)] #reach[i][0] == 1 表示从i出发，奇数次跳跃后能到达最后一个，reach[i][1]表示偶数次。。。\n",
    "\n",
    "        reach[-1] = [1, 1]\n",
    "        had = dict()\n",
    "        q = SortedList()\n",
    "        had[arr[-1]] = n - 1\n",
    "        q.add(arr[-1])\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            x = arr[i]\n",
    "            #奇数跳\n",
    "            index = q.bisect_left(x)\n",
    "            if index < len(q): \n",
    "                j = had[q[index]]\n",
    "                reach[i][0] = reach[j][1]\n",
    "\n",
    "            #偶数跳\n",
    "            index = q.bisect_right(x)\n",
    "            if index > 0:\n",
    "                j = had[q[index-1]]\n",
    "                reach[i][1] = reach[j][0]\n",
    "\n",
    "            if reach[i][0]:\n",
    "                ans += 1 \n",
    "\n",
    "\n",
    "            if x in had:\n",
    "                had[x] = i\n",
    "                continue\n",
    "            else:\n",
    "                had[x] = i\n",
    "                q.add(x)\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        def calc_nexts(idx: List[int]) -> List[int]:\n",
    "            nexts = [-1 for _ in range(n)]\n",
    "            s = []\n",
    "            for i in idx:\n",
    "                while s and i > s[-1]:\n",
    "                    nexts[s.pop()] = i\n",
    "                s.append(i)\n",
    "            return nexts\n",
    "        \n",
    "        odd_nexts = calc_nexts(sorted(range(n), key=lambda i: (arr[i], i)))\n",
    "        even_nexts = calc_nexts(sorted(range(n), key=lambda i: (-arr[i], i)))\n",
    "\n",
    "        odd_goods = [False for _ in range(n)]\n",
    "        even_goods = [False for _ in range(n)]\n",
    "        odd_goods[-1] = even_goods[-1] = True\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if odd_nexts[i] != -1:\n",
    "                odd_goods[i] = even_goods[odd_nexts[i]]\n",
    "            if even_nexts[i] != -1:\n",
    "                even_goods[i] = odd_goods[even_nexts[i]]\n",
    "        return sum(odd_goods)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        def f(nums):\n",
    "            res = [-1]*n\n",
    "            st = []\n",
    "            for x in nums:\n",
    "                while st and st[-1] < x:\n",
    "                    res[st.pop()] = x\n",
    "                st.append(x)\n",
    "            return res\n",
    "\n",
    "        a = f(sorted(range(n),key=lambda i:(arr[i],i)))\n",
    "        b = f(sorted(range(n),key=lambda i:(-arr[i],i)))\n",
    "        \n",
    "        dp = [[False,False] for _ in range(n)]\n",
    "        dp[-1] = [True,True]\n",
    "        ans = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if a[i] != -1 and dp[a[i]][1]:\n",
    "                dp[i][0] = True\n",
    "                ans += 1\n",
    "            if b[i] != -1 and dp[b[i]][0]:\n",
    "                dp[i][1] = True\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        indexSorted = sorted(range(len(arr)), key=lambda x: (arr[x], x))\n",
    "        indexSortedReverse = sorted(range(len(arr)), key=lambda x: (-arr[x], x))\n",
    "        import heapq\n",
    "        heap = []\n",
    "        oddJumps = [-1] * len(arr)\n",
    "        oddJumps[-1] = -2\n",
    "        for i, index in enumerate(indexSorted):\n",
    "            num = arr[index]\n",
    "            while heap:\n",
    "                indexHeap = heap[0]\n",
    "                numHeap = arr[indexHeap]\n",
    "                if indexHeap < index:\n",
    "                    oddJumps[indexHeap] = index\n",
    "                    heapq.heappop(heap)\n",
    "                else:\n",
    "                    break\n",
    "            heapq.heappush(heap, index)\n",
    "\n",
    "        heapReverse = []\n",
    "        evenJumps = [-1] * len(arr)\n",
    "        evenJumps[-1] = -2\n",
    "        for i, index in enumerate(indexSortedReverse):\n",
    "            num = arr[index]\n",
    "            while heapReverse:\n",
    "                indexHeap = heapReverse[0]\n",
    "                numHeap = arr[index]\n",
    "                if indexHeap < index:\n",
    "                    evenJumps[indexHeap] = index\n",
    "                    heapq.heappop(heapReverse)\n",
    "                else:\n",
    "                    break\n",
    "            heapq.heappush(heapReverse, index)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(arr)-2, -1, -1):\n",
    "            if oddJumps[i] != -1 and evenJumps[oddJumps[i]] == -2:\n",
    "                oddJumps[i] = -2\n",
    "            if evenJumps[i] != -1 and oddJumps[evenJumps[i]] == -2:\n",
    "                evenJumps[i] = -2\n",
    "        return oddJumps.count(-2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        stack = []\n",
    "        mx = [-1] * n\n",
    "        idx = sorted(range(n), key=lambda x: (arr[x], x))\n",
    "\n",
    "        for x in idx:\n",
    "            while stack and stack[-1] < x:\n",
    "                mx[stack.pop()] = x\n",
    "            stack.append(x)\n",
    "\n",
    "        mi = [-1] * n\n",
    "        idx = sorted(range(n), key=lambda x: (-arr[x], x))\n",
    "        stack = []\n",
    "        for x in idx:\n",
    "            while stack and stack[-1] < x:\n",
    "                mi[stack.pop()] = x\n",
    "            stack.append(x)\n",
    "        odd = [False] * n\n",
    "        even = [False] * n\n",
    "        odd[-1] = even[-1] = True\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if mx[i] != -1:\n",
    "                odd[i] = even[mx[i]]\n",
    "            if mi[i] != -1:\n",
    "                even[i] = odd[mi[i]]\n",
    "        # print(odd, even)\n",
    "        return sum(odd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 1\n",
    "        # 奇跳跃和偶跳跃\n",
    "        odd = [0] * n\n",
    "        even = [0] * n\n",
    "        odd[-1], even[-1] = 1, 1\n",
    "\n",
    "        # 每个数下个能跳到的下标\n",
    "        def get(a):\n",
    "            ans = [None] * n\n",
    "            st = []\n",
    "            for i in a:\n",
    "                while st and i > st[-1]:\n",
    "                    ans[st.pop()] = i\n",
    "                st.append(i)\n",
    "            return ans\n",
    "\n",
    "        a = sorted(range(n), key=lambda x: (arr[x], x))\n",
    "        oddjump = get(a)\n",
    "        b = sorted(range(n), key=lambda x: (-arr[x], x))\n",
    "        evenjump = get(b)\n",
    "\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if oddjump[i]:\n",
    "                odd[i] = even[oddjump[i]]\n",
    "            if evenjump[i]:\n",
    "                even[i] = odd[evenjump[i]]\n",
    "        return sum(odd)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        \n",
    "        a,b = [-1]*n,[-1]*n\n",
    "        st = []\n",
    "        nums = sorted(range(n),key=lambda i:(arr[i],i))\n",
    "        for x in nums:\n",
    "            while st and st[-1] < x:\n",
    "                a[st.pop()] = x\n",
    "            st.append(x)\n",
    "        st = []\n",
    "        nums = sorted(range(n),key=lambda i:(-arr[i],i))\n",
    "        for x in nums:\n",
    "            while st and st[-1] < x:\n",
    "                b[st.pop()] = x\n",
    "            st.append(x)\n",
    "        \n",
    "        dp = [[False,False] for _ in range(n)]\n",
    "        dp[-1] = [True,True]\n",
    "        ans = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if a[i] != -1 and dp[a[i]][1]:\n",
    "                dp[i][0] = True\n",
    "                ans += 1\n",
    "            if b[i] != -1 and dp[b[i]][0]:\n",
    "                dp[i][1] = True\n",
    "        for x in zip(range(n),arr,a,b,dp): print(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        data = [(arr[i], i) for i in range(len(arr))]\n",
    "        data.sort()\n",
    "        #print(data)\n",
    "        nextJ = [[-1, -1] for _ in range(len(arr))]\n",
    "        for i in range(len(data)):\n",
    "            num, position = data[i]\n",
    "            cur = i\n",
    "            while cur + 1 < len(data):\n",
    "                if data[cur + 1][1] > position:\n",
    "                    nextJ[position][0] = data[cur + 1][1]\n",
    "                    break\n",
    "                else:\n",
    "                    cur += 1\n",
    "            cur = i\n",
    "            if cur + 1 < len(arr) and data[cur + 1][0] == num:\n",
    "                nextJ[position][1] = data[cur + 1][1]\n",
    "            else:\n",
    "                while cur - 1 >= 0:\n",
    "                    if nextJ[position][1] == -1:\n",
    "                        if data[cur - 1][1] > position:\n",
    "                            nextJ[position][1] = data[cur - 1][1]\n",
    "                    elif data[cur - 1][0] == data[cur][0] and data[cur - 1][1] > position:\n",
    "                        nextJ[position][1] = data[cur - 1][1]\n",
    "                    else:\n",
    "                        break\n",
    "                    cur -= 1\n",
    "        print(nextJ)\n",
    "        res = 0\n",
    "        des = len(arr) - 1\n",
    "        nextJ[-1][0] = des\n",
    "        nextJ[-1][1] = des\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            if nextJ[i][0] != -1:\n",
    "                nextJ[i][0] = nextJ[nextJ[i][0]][1]\n",
    "            if nextJ[i][1] != -1:\n",
    "                nextJ[i][1] = nextJ[nextJ[i][1]][0]\n",
    "            if nextJ[i][0] == des:\n",
    "                res += 1\n",
    "        print(nextJ)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        next_odd = [-1] * n\n",
    "        next_even = [-1] * n\n",
    "        unorder = [(i, arr[i]) for i in range(len(arr))]\n",
    "        odd_order = sorted(unorder, key=lambda x:(x[1], x[0]))\n",
    "        even_order = sorted(unorder, key=lambda x:(x[1], -x[0]), reverse=True)\n",
    "        stack = []\n",
    "        for i, _ in odd_order:\n",
    "            while len(stack) > 0 and stack[-1] < i:\n",
    "                top = stack.pop(-1)\n",
    "                next_odd[top] = i\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i, _ in even_order:\n",
    "            while len(stack) > 0 and stack[-1] < i:\n",
    "                top = stack.pop(-1)\n",
    "                next_even[top] = i\n",
    "            stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            step = 1\n",
    "            cursor = i\n",
    "            while cursor != n-1 and cursor != -1:\n",
    "                if step % 2 == 1:\n",
    "                    next = next_odd[cursor]\n",
    "                else:\n",
    "                    next = next_even[cursor]\n",
    "                cursor = next\n",
    "                step += 1\n",
    "            if cursor == n-1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        g = [[-1]*2 for _ in range(n)]\n",
    "\n",
    "        # 奇数跳，向后找大于等于自己的最小位置\n",
    "        stack = []\n",
    "        for x,i in sorted((x,i) for i,x in enumerate(arr)):\n",
    "            # 单调栈，存储下标，递减\n",
    "            # 由于数组按值和下标从小到大排序，一旦遇到当前下标大于栈顶元素\n",
    "            # 则栈中元素对应的数组值都是小于当前下标对应的元素值的，下标小，值也小，满足奇数跳跃条件，栈中元素可以更新答案\n",
    "            while stack and stack[-1] < i:\n",
    "                g[stack.pop()][1] = i\n",
    "            stack.append(i)\n",
    "\n",
    "        # 偶数跳，向后找小于等于自己的最小位置\n",
    "        # 排序改为按值降序，下标升序\n",
    "        stack = []\n",
    "        for x,i in sorted((-x,i) for i,x in enumerate(arr)):\n",
    "            # 单调栈，存储下标，递减\n",
    "            # 由于数组按值从大到小排序，一旦遇到当前下标大于栈顶元素\n",
    "            # 则栈中元素对应的数组值都是大于当前下标对应的元素值的，下标小，值大，满足偶数跳跃条件，栈中元素可以更新答案\n",
    "            while stack and stack[-1] < i:\n",
    "                g[stack.pop()][0] = i\n",
    "            stack.append(i)\n",
    "\n",
    "        f = [[0]*2 for _ in range(n)] # f[i][0],f[i][1] 从i开始偶数跳和奇数跳最后能否跳到n-1\n",
    "        f[n - 1][0] = f[n - 1][1] = 1\n",
    "        ans = 1\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            # 当前偶数跳，取决于下次奇数跳\n",
    "            f[i][0] = f[g[i][0]][1] if g[i][0] != -1 else 0\n",
    "            # 当前奇数跳，取决于下次偶数跳\n",
    "            f[i][1] = f[g[i][1]][0] if g[i][1] != -1 else 0\n",
    "            ans += f[i][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        next_odd = [-1] * n\n",
    "        next_even = [-1] * n\n",
    "        unorder = [(i, arr[i]) for i in range(len(arr))]\n",
    "        odd_order = sorted(unorder, key=lambda x:(x[1], x[0]))\n",
    "        even_order = sorted(unorder, key=lambda x:(x[1], -x[0]), reverse=True)\n",
    "        stack = []\n",
    "        for i, _ in odd_order:\n",
    "            while len(stack) > 0 and stack[-1] < i:\n",
    "                top = stack.pop(-1)\n",
    "                next_odd[top] = i\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i, _ in even_order:\n",
    "            while len(stack) > 0 and stack[-1] < i:\n",
    "                top = stack.pop(-1)\n",
    "                next_even[top] = i\n",
    "            stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            step = 1\n",
    "            cursor = i\n",
    "            while cursor != n-1 and cursor != -1:\n",
    "                if step % 2 == 1:\n",
    "                    next = next_odd[cursor]\n",
    "                else:\n",
    "                    next = next_even[cursor]\n",
    "                cursor = next\n",
    "                step += 1\n",
    "            if cursor == n-1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        next_odd = [-1] * n\n",
    "        next_even = [-1] * n\n",
    "        unorder = [(i, arr[i]) for i in range(len(arr))]\n",
    "        odd_order = sorted(unorder, key=lambda x:(x[1], x[0]))\n",
    "        even_order = sorted(unorder, key=lambda x:(x[1], -x[0]), reverse=True)\n",
    "        stack = []\n",
    "        for i, _ in odd_order:\n",
    "            while len(stack) > 0 and stack[-1] < i:\n",
    "                top = stack.pop(-1)\n",
    "                next_odd[top] = i\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i, _ in even_order:\n",
    "            while len(stack) > 0 and stack[-1] < i:\n",
    "                top = stack.pop(-1)\n",
    "                next_even[top] = i\n",
    "            stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            step = 1\n",
    "            cursor = i\n",
    "            while cursor != n-1 and cursor != -1:\n",
    "                if step % 2 == 1:\n",
    "                    next = next_odd[cursor]\n",
    "                else:\n",
    "                    next = next_even[cursor]\n",
    "                cursor = next\n",
    "                step += 1\n",
    "            if cursor == n-1:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ind = list(range(n))\n",
    "        dct = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dct[arr[i]].append(i)\n",
    "\n",
    "        right_odd = [-1] * n\n",
    "        pre = SortedList()\n",
    "        dct = dict()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            num = arr[i]\n",
    "            j = pre.bisect_left(num)\n",
    "            if 0 <= j < len(pre):\n",
    "                right_odd[i] = dct[pre[j]]\n",
    "            if num not in dct:\n",
    "                pre.add(num)\n",
    "            dct[num] = i\n",
    "\n",
    "\n",
    "        right_even = [-1] * n\n",
    "        pre = SortedList()\n",
    "        dct = dict()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            num = arr[i]\n",
    "            j = pre.bisect_right(num) - 1\n",
    "            if 0 <= j < len(pre):\n",
    "                right_even[i] = dct[pre[j]]\n",
    "            if num not in dct:\n",
    "                pre.add(num)\n",
    "            dct[num] = i\n",
    "\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        dp[-1] = [1, 1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if right_odd[i] != -1 and dp[right_odd[i]][1]:\n",
    "                dp[i][0] = 1\n",
    "            if right_even[i] != -1 and dp[right_even[i]][0]:\n",
    "                dp[i][1] = 1\n",
    "        return sum(x for x, _ in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[False, False] for _ in range(n)]\n",
    "        f[-1] = [True, True]\n",
    "        ordered_list = SortedList()\n",
    "        ordered_list.add([arr[-1], n -1])\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            x = arr[i]\n",
    "            # odd\n",
    "            odd_idx = ordered_list.bisect_left([x, i])\n",
    "            if odd_idx < len(ordered_list):\n",
    "                idx = ordered_list[odd_idx][1]\n",
    "                f[i][0] |= f[idx][1]\n",
    "            # even\n",
    "            larger_idx = ordered_list.bisect_right([x, inf])\n",
    "            if larger_idx > 0:\n",
    "                samller_val = arr[ordered_list[larger_idx - 1][1]]\n",
    "                even_idx = ordered_list.bisect_left([samller_val, -1])\n",
    "                f[i][1] |= f[ordered_list[even_idx][1]][0]\n",
    "                # print(i, even_idx)\n",
    "            ordered_list.add([x, i])\n",
    "        # print(f)\n",
    "        return sum([odd for odd, even in f])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        g = [[-1]*2 for _ in range(n)]\n",
    "\n",
    "        # 奇数跳，向后找大于等于自己的最小位置\n",
    "        stack = []\n",
    "        for x,i in sorted((x,i) for i,x in enumerate(arr)):\n",
    "            # 单调栈，存储下标，递减\n",
    "            # 由于数组按值和下标从小到大排序，一旦遇到当前下标大于栈顶元素\n",
    "            # 则栈中元素对应的数组值都是小于当前下标对应的元素值的，下标小，值也小，满足奇数跳跃条件，栈中元素可以更新答案\n",
    "            while stack and stack[-1] < i:\n",
    "                g[stack.pop()][1] = i\n",
    "            stack.append(i)\n",
    "\n",
    "        # 偶数跳，向后找小于等于自己的最小位置\n",
    "        # 排序改为按值降序，下标升序\n",
    "        stack = []\n",
    "        for x,i in sorted((-x,i) for i,x in enumerate(arr)):\n",
    "            # 单调栈，存储下标，递减\n",
    "            # 由于数组按值从大到小排序，一旦遇到当前下标大于栈顶元素\n",
    "            # 则栈中元素对应的数组值都是大于当前下标对应的元素值的，下标小，值大，满足偶数跳跃条件，栈中元素可以更新答案\n",
    "            while stack and stack[-1] < i:\n",
    "                g[stack.pop()][0] = i\n",
    "            stack.append(i)\n",
    "\n",
    "        f = [[0]*2 for _ in range(n)]\n",
    "        f[n - 1][0] = f[n - 1][1] = 1\n",
    "        ans = 1\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            f[i][0] = f[g[i][0]][1] if g[i][0] != -1 else 0\n",
    "            f[i][1] = f[g[i][1]][0] if g[i][1] != -1 else 0\n",
    "            ans += f[i][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "\n",
    "        odd_nxt = [N] * N\n",
    "        sd = SortedDict()\n",
    "        sd[arr[-1]] = N - 1\n",
    "        for i in range(N - 2, -1, -1):\n",
    "            idx = sd.bisect_left(arr[i])\n",
    "            if idx < len(sd):\n",
    "                odd_nxt[i] = sd[sd.keys()[idx]]\n",
    "            sd[arr[i]] = i\n",
    "\n",
    "        even_nxt = [N] * N\n",
    "        sd = SortedDict()\n",
    "        sd[arr[-1]] = N - 1\n",
    "        for i in range(N - 2, -1, -1):\n",
    "            idx = sd.bisect_right(arr[i]) - 1\n",
    "            if idx >= 0:\n",
    "                even_nxt[i] = sd[sd.keys()[idx]]\n",
    "            sd[arr[i]] = i\n",
    "\n",
    "        steps = [[0] * 2 for _ in range(N)]\n",
    "        steps[-1][0], steps[-1][1] = 1, 1\n",
    "        for i in range(N - 2, -1, -1):\n",
    "            steps[i][0] = steps[even_nxt[i]][1] if even_nxt[i] != N else 0\n",
    "            steps[i][1] = steps[odd_nxt[i]][0] if odd_nxt[i] != N else 0\n",
    "        return sum(steps[i][1] for i in range(N))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        odd = [0]*n\n",
    "        even = [0]*n\n",
    "\n",
    "        from sortedcontainers import SortedList\n",
    "        stack = SortedList()\n",
    "        for i in range(n-1, -1, -1):\n",
    "            idx = bisect.bisect(stack, (arr[i], i))\n",
    "            odd[i] = stack[idx][1] if idx < len(stack) else None\n",
    "            if idx < len(stack) and stack[idx][0] == arr[i]:\n",
    "                even[i] = stack[idx][1]\n",
    "            else:\n",
    "                while(idx-1 >= 1 and stack[idx-1][0] == stack[idx-2][0]):\n",
    "                    idx -= 1\n",
    "                even[i] = stack[idx-1][1] if idx-1 >= 0 else None\n",
    "            stack.add((arr[i], i))\n",
    "        \n",
    "        # print(odd, even)\n",
    "\n",
    "        dp = [[False, False] for _ in range(n)]\n",
    "        dp[-1] = [True, True]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if odd[i] == None:\n",
    "                dp[i][0] = False\n",
    "            else:\n",
    "                dp[i][0] = dp[odd[i]][1]\n",
    "            \n",
    "            if even[i] == None:\n",
    "                dp[i][1] = False\n",
    "            else:\n",
    "                dp[i][1] = dp[even[i]][0]\n",
    "        \n",
    "        return sum([1 if dp[i][0] else 0 for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "        index = {}\n",
    "        odd_jump = [-1] * l\n",
    "        even_jump = [-1] * l\n",
    "        sort = []\n",
    "        for i in range(l-1, -1, -1):\n",
    "            n = arr[i]\n",
    "            hi = bisect.bisect_left(sort, n)\n",
    "            if hi < len(sort):\n",
    "                odd_jump[i] = index[sort[hi]]\n",
    "            lo = bisect.bisect_right(sort, n) - 1\n",
    "            if lo >= 0:\n",
    "                even_jump[i] = index[sort[lo]]\n",
    "            index[n] = i\n",
    "            if hi >= len(sort) or sort[hi] != n:\n",
    "                sort.insert(hi, n)\n",
    "        \n",
    "        @cache\n",
    "        def judge(idx, mode=1):\n",
    "            if idx == -1:\n",
    "                return False\n",
    "            if idx == l-1:\n",
    "                return True\n",
    "            if mode: # odd\n",
    "                nxt = odd_jump[idx]\n",
    "                return judge(nxt, 0)\n",
    "            else: # even\n",
    "                nxt = even_jump[idx]\n",
    "                return judge(nxt, 1)\n",
    "        cnt = 1\n",
    "        odd = [0] * l\n",
    "        even = [0] * l\n",
    "        odd[-1] = even[-1] = 1\n",
    "        for i in range(l-2, -1, -1):\n",
    "            if odd_jump[i] != -1:\n",
    "                odd[i] = even[odd_jump[i]]\n",
    "            if even_jump[i] != -1:\n",
    "                even[i] = odd[even_jump[i]]\n",
    "            if odd[i]:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        if n==1:\n",
    "            return 1\n",
    "\n",
    "\n",
    "        # how to construct dp_large and dp_small?\n",
    "        dp_large = [-1]*n\n",
    "        dp_small = [-1]*n \n",
    "\n",
    "        num_index = [(arr[i],i) for i in range(n) ]\n",
    "        num_index = sorted(num_index,key=lambda x:[x[0],x[1]])\n",
    "\n",
    "        i = 1\n",
    "        stack = [num_index[0][1]]\n",
    "        while i<n:\n",
    "            j = num_index[i][1]\n",
    "            while stack and j>stack[-1]:\n",
    "                k = stack.pop()\n",
    "                if dp_large[k]==-1:\n",
    "                    dp_large[k] = j \n",
    "            stack.append(j)\n",
    "            i += 1\n",
    "        \n",
    "\n",
    "        num_index = [(arr[i],i) for i in range(n) ]\n",
    "        num_index = sorted(num_index,key=lambda x:[-x[0],x[1]])\n",
    "\n",
    "        i = 1\n",
    "        stack = [num_index[0][1]]\n",
    "        while i<n:\n",
    "            j = num_index[i][1]\n",
    "            while stack and j>stack[-1]:\n",
    "                k = stack.pop()\n",
    "                if dp_small[k]==-1:\n",
    "                    dp_small[k] = j \n",
    "            stack.append(j)\n",
    "            i += 1\n",
    "           \n",
    "        \n",
    "        dp = [[False]*2 for _ in range(n)]\n",
    "        dp[n-1][0], dp[n-1][1] = True, True \n",
    "\n",
    "        count = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            \n",
    "            if dp_small[i]!= -1:\n",
    "                j = dp_small[i]\n",
    "                dp[i][0] = dp[j][1]  # next even jump\n",
    "\n",
    "            if dp_large[i]!=-1:\n",
    "                j = dp_large[i]\n",
    "                dp[i][1] = dp[j][0]   # next odd jump\n",
    "            if  dp[i][1]:\n",
    "                count += 1\n",
    "        return count \n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        if n==1:\n",
    "            return 1\n",
    "        y=[[arr[-1],n-1]]\n",
    "        x=[[arr[-1],-(n-1)]]\n",
    "        odd=[-1]*n\n",
    "        even=[-1]*n\n",
    "        for i in range (1,n):\n",
    "            u=bisect.bisect_left(y,[arr[n-1-i],n-1-i])\n",
    "            if u<len(y):\n",
    "                odd[n-1-i]=y[u][1]\n",
    "            bisect.insort(y,[arr[n-1-i],n-1-i])\n",
    "        \n",
    "        for i in range (1,n):\n",
    "            u=bisect.bisect_left(x,[arr[n-1-i],-(n-1-i)])\n",
    "            if u>0:\n",
    "                even[n-1-i]=-x[u-1][1]\n",
    "            bisect.insort(x,[arr[n-1-i],-(n-1-i)])\n",
    "        \n",
    "        ans=1\n",
    "        for i in range (0,n-1):\n",
    "            j=1\n",
    "            pos=i\n",
    "            while 1:\n",
    "                if pos==n-1:\n",
    "                    ans+=1\n",
    "                    break\n",
    "\n",
    "                if j%2==1:\n",
    "                    if odd[pos]!=-1:\n",
    "                        pos=odd[pos]\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "                else:\n",
    "                    if even[pos]!=-1:\n",
    "                        pos=even[pos]\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        g = [[-1]*2 for _ in range(n)]\n",
    "\n",
    "        def solve(a,flag):\n",
    "            stack = []\n",
    "            for x,i in a:\n",
    "                # 单调栈，存储下标，递减\n",
    "                while stack and stack[-1] < i:\n",
    "                    g[stack.pop()][flag] = i\n",
    "                stack.append(i)\n",
    "\n",
    "        solve(sorted((x,i) for i,x in enumerate(arr)),1)\n",
    "\n",
    "        solve(sorted((-x,i) for i,x in enumerate(arr)),0)\n",
    "\n",
    "        f = [[0]*2 for _ in range(n)] # f[i][0],f[i][1] 从i开始偶数跳和奇数跳最后能否跳到n-1\n",
    "        f[n - 1][0] = f[n - 1][1] = 1\n",
    "        ans = 1\n",
    "        for i in range(n - 2,-1,-1):\n",
    "            # 当前偶数跳，取决于下次奇数跳\n",
    "            f[i][0] = f[g[i][0]][1] if g[i][0] != -1 else 0\n",
    "            # 当前奇数跳，取决于下次偶数跳\n",
    "            f[i][1] = f[g[i][1]][0] if g[i][1] != -1 else 0\n",
    "            ans += f[i][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        if n==1:\n",
    "            return 1\n",
    "\n",
    "\n",
    "        # how to construct dp_large and dp_small?\n",
    "        dp_large = [-1]*n\n",
    "        dp_small = [-1]*n \n",
    "\n",
    "        num_index = [(arr[i],i) for i in range(n) ]\n",
    "        num_index = sorted(num_index,key=lambda x:[x[0],x[1]])\n",
    "        index_list = [x[1] for x in num_index]\n",
    "\n",
    "        def make(B):\n",
    "\n",
    "            i = 1\n",
    "            stack = [B[0]]\n",
    "            ans = [-1]*n\n",
    "            while i<n:\n",
    "                j = B[i]\n",
    "                while stack and j>stack[-1]:\n",
    "                    k = stack.pop()\n",
    "                    if ans[k]==-1:\n",
    "                        ans[k] = j \n",
    "                stack.append(j)\n",
    "                i += 1\n",
    "            return ans \n",
    "        \n",
    "        dp_large = make(index_list)\n",
    "        \n",
    "\n",
    "        num_index = [(arr[i],i) for i in range(n) ]\n",
    "        num_index = sorted(num_index,key=lambda x:[-x[0],x[1]])\n",
    "        index_list = [x[1] for x in num_index]\n",
    "\n",
    "        dp_small = make(index_list)\n",
    "\n",
    "        \n",
    "        dp = [[False]*2 for _ in range(n)]\n",
    "        dp[n-1][0], dp[n-1][1] = True, True \n",
    "\n",
    "        count = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            \n",
    "            if dp_small[i]!= -1:\n",
    "                j = dp_small[i]\n",
    "                dp[i][0] = dp[j][1]  # next even jump\n",
    "\n",
    "            if dp_large[i]!=-1:\n",
    "                j = dp_large[i]\n",
    "                dp[i][1] = dp[j][0]   # next odd jump\n",
    "            if  dp[i][1]:\n",
    "                count += 1\n",
    "        return count \n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        so = SortedList()\n",
    "        odd = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(so)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if so[mid][0] >= arr[i]:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if so and so[l][0] >= arr[i]:\n",
    "                odd[i] = so[l][1]\n",
    "            else:\n",
    "                odd[i] = i\n",
    "            so.add([arr[i], i])\n",
    "        se = SortedList()\n",
    "        even = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(se)-1\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) // 2\n",
    "                if se[mid][0] <= arr[i]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if se and se[l][0] <= arr[i]:\n",
    "                even[i] = se[l][1]\n",
    "                if arr[i] == se[l][0]:\n",
    "                    se[l][1] = i\n",
    "                    continue                                                                   \n",
    "            else:\n",
    "                even[i] = i\n",
    "            se.add([arr[i], i])\n",
    "        \n",
    "        f = [[False, False] for _ in range(n)]\n",
    "        f[-1] = [True, True]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if odd[i] == i:\n",
    "                f[i][0] = False\n",
    "            else:\n",
    "                f[i][0] = f[odd[i]][1]\n",
    "            if even[i] == i:\n",
    "                f[i][1] = False\n",
    "            else:\n",
    "                f[i][1] = f[even[i]][0]\n",
    "        return sum(1 if f[i][0] == True else 0 for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[False] * 2 for _ in range(n)]\n",
    "        dp[n - 1] = [True] * 2\n",
    "        st = SortedList()\n",
    "        st2 = SortedList()\n",
    "        st2.add((-arr[-1], n - 1))\n",
    "        st.add((arr[-1], n - 1))\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            idx = st.bisect_left((arr[i], -1))\n",
    "            if idx != len(st):\n",
    "                _, j = st[idx]\n",
    "                dp[i][1] = dp[i][1] or dp[j][0]\n",
    "            idx1 = st2.bisect_right((-arr[i], -1))\n",
    "            if idx1 != len(st2):\n",
    "                _, j = st2[idx1]\n",
    "                dp[i][0] = dp[i][0] or dp[j][1]\n",
    "            \n",
    "            st.add((arr[i], i))\n",
    "            st2.add((-arr[i], i))\n",
    "        # print(dp)\n",
    "        ans = 1\n",
    "        for i in range(n - 1):\n",
    "            ans += int(dp[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        so = SortedList()\n",
    "        odd = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(so)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if so[mid][0] >= arr[i]:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if so and so[l][0] >= arr[i]:\n",
    "                odd[i] = so[l][1]\n",
    "            else:\n",
    "                odd[i] = i\n",
    "            so.add([arr[i], i])\n",
    "        se = SortedList()\n",
    "        even = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(se)-1\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) // 2\n",
    "                if se[mid][0] <= arr[i]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if se and se[l][0] <= arr[i]:\n",
    "                even[i] = se[l][1]\n",
    "                if arr[i] == se[l][0]:\n",
    "                    se[l][1] = i\n",
    "                    continue\n",
    "            else:\n",
    "                even[i] = i\n",
    "            se.add([arr[i], i])\n",
    "        # o(n)解法\n",
    "        # dp[i][0]表示以i为起点，当前跳的是奇数步是否可行\n",
    "        # dp[i][1]表示以i为起点，当前跳的是偶数步是否可行\n",
    "        \n",
    "        dp = [[False, False] for _ in range(n)]\n",
    "        dp[-1] = [True, True]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if odd[i] == i:\n",
    "                dp[i][0] = False\n",
    "            else:\n",
    "                dp[i][0] = dp[odd[i]][1]\n",
    "            \n",
    "            if even[i] == i:\n",
    "                dp[i][1] = False\n",
    "            else:\n",
    "                dp[i][1] = dp[even[i]][0]\n",
    "        \n",
    "        return sum([1 if dp[i][0] else 0 for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        so = SortedList()\n",
    "        odd = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(so)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if so[mid][0] >= arr[i]:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if so and so[l][0] >= arr[i]:\n",
    "                odd[i] = so[l][1]\n",
    "                if arr[i] == so[l][0]:\n",
    "                    so[l][1] = i\n",
    "                    continue\n",
    "            else:\n",
    "                odd[i] = i\n",
    "            so.add([arr[i], i])\n",
    "        se = SortedList()\n",
    "        even = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(se)-1\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) // 2\n",
    "                if se[mid][0] <= arr[i]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if se and se[l][0] <= arr[i]:\n",
    "                even[i] = se[l][1]\n",
    "                if arr[i] == se[l][0]:\n",
    "                    se[l][1] = i\n",
    "                    continue\n",
    "            else:\n",
    "                even[i] = i\n",
    "            se.add([arr[i], i])\n",
    "        dp = [[False, False] for _ in range(n)]\n",
    "        dp[-1] = [True, True]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if odd[i] == i:\n",
    "                dp[i][0] = False\n",
    "            else:\n",
    "                dp[i][0] = dp[odd[i]][1]\n",
    "            \n",
    "            if even[i] == i:\n",
    "                dp[i][1] = False\n",
    "            else:\n",
    "                dp[i][1] = dp[even[i]][0]\n",
    "        \n",
    "        return sum([1 if dp[i][0] else 0 for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[False] * 2 for _ in range(n)]\n",
    "        dp[n - 1] = [True] * 2\n",
    "        st = SortedList()\n",
    "        st2 = SortedList()\n",
    "        st2.add((-arr[-1], n - 1))\n",
    "        st.add((arr[-1], n - 1))\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            idx = st.bisect_left((arr[i], -1))\n",
    "            if idx != len(st):\n",
    "                _, j = st[idx]\n",
    "                dp[i][1] = dp[i][1] or dp[j][0]\n",
    "            idx1 = st2.bisect_left((-arr[i], -1))\n",
    "            if idx1 != len(st2):\n",
    "                _, j = st2[idx1]\n",
    "                dp[i][0] = dp[i][0] or dp[j][1]\n",
    "            \n",
    "            st.add((arr[i], i))\n",
    "            st2.add((-arr[i], i))\n",
    "        # print(dp)\n",
    "        ans = 1\n",
    "        for i in range(n - 1):\n",
    "            ans += int(dp[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        so = SortedList()\n",
    "        odd = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(so)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if so[mid][0] >= arr[i]:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if so and so[l][0] >= arr[i]:\n",
    "                odd[i] = so[l][1]\n",
    "                if arr[i] == so[l][0]:\n",
    "                    so[l][1] = i\n",
    "                    continue\n",
    "            else:\n",
    "                odd[i] = i\n",
    "            so.add([arr[i], i])\n",
    "        se = SortedList()\n",
    "        even = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(se)-1\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) // 2\n",
    "                if se[mid][0] <= arr[i]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if se and se[l][0] <= arr[i]:\n",
    "                even[i] = se[l][1]\n",
    "                if arr[i] == se[l][0]:\n",
    "                    se[l][1] = i\n",
    "                    continue\n",
    "            else:\n",
    "                even[i] = i\n",
    "            se.add([arr[i], i])\n",
    "        def dfs(x, cnt):\n",
    "            if x == n-1:\n",
    "                return True\n",
    "            if cnt % 2 == 1:\n",
    "                nxt = odd[x]\n",
    "                if nxt == x:\n",
    "                    return False\n",
    "                if dfs(nxt, cnt + 1):\n",
    "                    return True\n",
    "            else:\n",
    "                nxt = even[x]\n",
    "                if nxt == x:\n",
    "                    return False\n",
    "                if dfs(nxt, cnt + 1):\n",
    "                    return True\n",
    "            return False\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += dfs(i, 1) == True\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        # 从右往左遍历，SortedList记录值，然后二分sortedlist，找到大于该数的最小值\n",
    "        # 从右往左遍历，SortedList记录值，然后二分sortedlist，找到小于该数的最大值\n",
    "        # 得到两个数组，然后从零开始dfs，如果最后跳到了结尾，把经过的路径全部更新成True，否则更新成false\n",
    "        # 最后统一true的数量即可\n",
    "        n = len(arr)\n",
    "        vis = [False] * n\n",
    "        so = SortedList()\n",
    "        odd = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(so)-1\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if so[mid][0] >= arr[i]:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if so and so[l][0] >= arr[i]:\n",
    "                odd[i] = so[l][1]\n",
    "                if arr[i] == so[l][0]:\n",
    "                    so[l][1] = i\n",
    "                    continue\n",
    "            else:\n",
    "                odd[i] = i\n",
    "            so.add([arr[i], i])\n",
    "        se = SortedList()\n",
    "        even = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            l, r = 0, len(se)-1\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) // 2\n",
    "                if se[mid][0] <= arr[i]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if se and se[l][0] <= arr[i]:\n",
    "                even[i] = se[l][1]\n",
    "                if arr[i] == se[l][0]:\n",
    "                    se[l][1] = i\n",
    "                    continue\n",
    "            else:\n",
    "                even[i] = i\n",
    "            se.add([arr[i], i])\n",
    "        print(odd, even)\n",
    "        vis = [False] * n\n",
    "        def dfs(x, cnt):\n",
    "            if x == n-1:\n",
    "                return True\n",
    "            if cnt % 2 == 1:\n",
    "                nxt = odd[x]\n",
    "                if nxt == x:\n",
    "                    return False\n",
    "                if dfs(nxt, cnt + 1):\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                nxt = even[x]\n",
    "                if nxt == x:\n",
    "                    return False\n",
    "                if dfs(nxt, cnt + 1):\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            return False\n",
    "        print(so, se)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                ans += dfs(i, 1) == True\n",
    "        print(vis)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# in the case of an odd jump\r\n",
    "# arr[j] can be arrived from arr[i], where arr[i] <= arr[j] and\r\n",
    "# arr[j] is minimum value in arr[j:], and\r\n",
    "# in the case of an even jump\r\n",
    "# arr[j] can be arrived from arr[i], where arr[i] >= arr[j] and\r\n",
    "# arr[j] is maximum value in arr[j:], and\r\n",
    "# with reversed traversal for sorted list, valid i->j pairs can be found\r\n",
    "# finally find all valid starting index as a path of odd - even - ...\r\n",
    "from sortedcontainers import SortedDict\r\n",
    "class Solution:\r\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\r\n",
    "        n = len(arr)\r\n",
    "        reachable = [[False] * 2 for _ in range(n)]\r\n",
    "        conn: list[list[list[int]]] = [[[], []] for _ in range(n)]\r\n",
    "        sd: dict[int, int] = SortedDict()\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            x = sd.bisect_left(arr[i])\r\n",
    "            if x < len(sd) and sd.keys()[x] == arr[i]:\r\n",
    "                conn[sd.values()[x]][0].append(i)\r\n",
    "                conn[sd.values()[x]][1].append(i)\r\n",
    "                sd[sd.keys()[x]] = i\r\n",
    "            else:\r\n",
    "                if x > 0:\r\n",
    "                    conn[sd.values()[x - 1]][0].append(i)\r\n",
    "                if x < len(sd):\r\n",
    "                    conn[sd.values()[x]][1].append(i)\r\n",
    "                sd.setdefault(arr[i], i)\r\n",
    "        \r\n",
    "        reachable[n - 1][0] = reachable[n - 1][1] = True\r\n",
    "        res = 0\r\n",
    "\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            if reachable[i][0]:\r\n",
    "                for j in conn[i][1]:\r\n",
    "                    reachable[j][1] = True\r\n",
    "\r\n",
    "            if reachable[i][1]:\r\n",
    "                res += 1\r\n",
    "                for j in conn[i][0]:\r\n",
    "                    reachable[j][0] = True\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n, vals, mp = len(arr), SortedList(), {}\n",
    "        connects = [[-1, -1] for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            val = arr[i]\n",
    "            idx = vals.bisect_left(val)\n",
    "            if idx == len(vals):\n",
    "                if vals: connects[i][1] = mp[vals[idx - 1]]\n",
    "                vals.add(val)\n",
    "            else:\n",
    "                connects[i][0] = mp[vals[idx]]\n",
    "                if vals[idx] == val: connects[i][1] = mp[val]\n",
    "                else:\n",
    "                    if idx > 0: connects[i][1] = mp[vals[idx - 1]]\n",
    "                    vals.add(val)\n",
    "            mp[val] = i\n",
    "        res = [[0, 0] for _ in range(n)]\n",
    "        def dfs(cur, st):\n",
    "            if res[cur][st] == 0:\n",
    "                if cur == n - 1: res[cur][st] = 1\n",
    "                else:\n",
    "                    nc = connects[cur][st]\n",
    "                    if nc == -1: res[cur][st] = -1\n",
    "                    else: res[cur][st] = dfs(nc, 1 - st)\n",
    "            return res[cur][st]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if dfs(i, 0) == 1: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        sl = SortedList()\n",
    "        odds_next = [-1] * n  # 每个arr[i]能奇数跳的位置\n",
    "        even_next = [-1] * n  # 每个arr[i]能偶数跳的位置\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            p = sl.bisect_left([arr[i], i])\n",
    "            if p != len(sl):\n",
    "                odds_next[i] = sl[p][1]\n",
    "            p = sl.bisect_left([arr[i], n])\n",
    "            if p != 0:\n",
    "                j = sl[p - 1][1]\n",
    "                p = sl.bisect_left([arr[j], 0])\n",
    "                even_next[i] = sl[p][1]\n",
    "            sl.add([arr[i], i])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, odds):\n",
    "            if i == n - 1:\n",
    "                return True\n",
    "            if odds:\n",
    "                j = odds_next[i]\n",
    "            else:\n",
    "                j = even_next[i]\n",
    "            if j == -1:\n",
    "                return False\n",
    "            return dfs(j, not odds)\n",
    "        res = [dfs(i, True) for i in range(n)]\n",
    "        # print(res)\n",
    "        return len([1 for x in res if x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def oddEvenJumps(self, arr: List[int]) -> int:\n",
    "        n, vals, mp = len(arr), SortedList(), {}\n",
    "        connects = [[-1, -1] for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            val = arr[i]\n",
    "            idx = vals.bisect_left(val)\n",
    "            if idx == len(vals):\n",
    "                if vals: connects[i][1] = mp[vals[idx - 1]]\n",
    "                vals.add(val)\n",
    "            else:\n",
    "                connects[i][0] = mp[vals[idx]]\n",
    "                if vals[idx] == val: connects[i][1] = mp[val]\n",
    "                else:\n",
    "                    if idx > 0: connects[i][1] = mp[vals[idx - 1]]\n",
    "                    vals.add(val)\n",
    "            mp[val] = i\n",
    "        res = [[0, 0] for _ in range(n)]\n",
    "        def dfs(cur, st):\n",
    "            if res[cur][st] == 0:\n",
    "                if cur == n - 1: res[cur][st] = 1\n",
    "                else:\n",
    "                    nc = connects[cur][st]\n",
    "                    if nc == -1: res[cur][st] = -1\n",
    "                    else: res[cur][st] = dfs(nc, 1 - st)\n",
    "            return res[cur][st]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if dfs(i, 0) == 1: ans += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
